/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/wildcard-matching
   @Language: C++
   @Datetime: 19-06-06 15:07
   */

// Method 1, Time 12ms
class Solution {
public:
	bool isMatch(string &s, string &p) {
		int j=0;
		for(int i=0, last=0, star=-1; i<s.length();){
			if(j<p.length() && (s[i]==p[j] || p[j]=='?')){
				++i;
				++j;
			}
			else if(j<p.length() && p[j]=='*'){
				last=i;
				star=j++;
			}
			else if(star!=-1){
				i=++last;
				j=star+1;
			}
			else return false;
		}
		for(; j<p.length() && p[j]=='*'; ++j);
		return j==p.length();
	}
};

// Method 2, dp, Time 176ms
class Solution {
public:
	bool isMatch(string &s, string &p) {
		int n=s.length(), m=p.length();
		vector<vector<bool> > dp(n+1,vector<bool>(m+1,false));
		dp[0][0]=true;
		for(int i=0; i<m; i++)
			if (p[i]=='*') dp[0][i+1]=dp[0][i];
		for(int i=0; i<n; i++){
			for (int j=0; j<m; j++){
				if (p[j]=='*'){
					dp[i+1][j+1] = dp[i][j] | dp[i][j+1] | dp[i+1][j];
				}
				else if (p[j]=='?'){
					dp[i+1][j+1] = dp[i][j];
				}
				else dp[i+1][j+1] = dp[i][j] & (s[i]==p[j]);
			}
		}
		return dp[n][m];
	}
};

// Method 3, recursion with memory, Time 760ms
class Solution {
	unordered_set<long> fails;
	bool isMatch(string &s, int i, string &p, int j){
		if(fails.count(((i+0L)<<32) | j)) return false;
		if(i==s.length() && j==p.length()) return true;
		if(j==p.length()) return false;
		if(i==s.length()){
			int star=0;
			for(int k=j; k<p.length() && p[k++]=='*'; ++star);
			return (star==p.length()-j);
		}
		if(s[i]==p[j] || p[j]=='?') {
			bool match=isMatch(s,i+1,p,j+1);
			if(!match) fails.insert(((i+1L)<<32) | (j+1L));
			return match;
		}
		if(p[j]=='*') {
			bool match=isMatch(s,i+1,p,j) || isMatch(s,i+1,p,j+1) || isMatch(s,i,p,j+1);
			if(!match){
				fails.insert(((i+1L)<<32) | j);
				fails.insert(((i+1L)<<32) | (j+1L));
				fails.insert(((i+0L)<<32) | (j+1L));
			}
			return match;
		}
		fails.insert(((i+0L)<<32) | j);
		return false;
	}
public:
	bool isMatch(string &s, string &p) {
		return isMatch(s,0,p,0);
	}
};

